#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> rt;
            if(nums.size() < 2) {
                return rt;
            }
            sort(nums.begin(),nums.end());
            int a,b,c;
            a=nums[0] + 1;
            for(int i = 0;i<nums.size() - 2;i++) {
                if(nums[i] == a ) continue;
                else a = nums[i] ;

                b=nums[i+1] + 1;
                for(int j = i+1;j<nums.size()-1;j++) {
                    if(nums[j] == b ) continue;
                    else b = nums[j];

                    c=nums[j+1] + 1;
                    for(int k = j+1;k<nums.size();k++) {
                        if(nums[k] == c ) continue;
                        else c = nums[k];

                        if(a+b+c==0){
                            vector<int> t;
                            t.push_back(a);
                            t.push_back(b);
                            t.push_back(c);
                            rt.push_back(t);
                        }
                    }
                }
            }
            return rt;
    }
    //双指针法
    vector<vector<int>> threeSum1(vector<int>& nums) {
            vector<vector<int>> rt;
            int len = nums.size();
            sort(nums.begin(),nums.end());
            for (int first=0;first < len; ++first) {
                //枚举和上一次数据不一样的数
                if (first > 0 && nums[first] == nums[first-1]) continue;
                //c对应指针数组最右端
                int third = len - 1;
                int target = -nums[first];
                //枚举b
                for(int second = first + 1 ;second < len ; ++second) {
                    //保证和上一次的数据不一样
                    if(second > first + 1 && nums[second] == nums[second - 1]) continue;
                    //保证b在c的左侧
                    while(second < third && nums[second] + nums[third] > target) third--;
                    if(second == third)break;
                    if (nums[second] + nums[third] == target ) rt.push_back({nums[first],nums[second],nums[third]});
                }
            }

            return rt;
    }
};


int main(){

    vector < vector<int> > ans;
    Solution sp;
    vector<int> nums = {-1,0,1,2,-1,-4};
    ans = sp.threeSum1(nums);
    cout<<"hello"<<endl;
    return 0;
}